package listStudy;

import common.utils.ListNode;

import java.util.ArrayList;

/**
 * 链表应该是面试时被提及最频繁的数据结构。链表的结构很简单，它由指针把若干个节点连接成链状结构。
 * 链表的创建、插入节点、删除节点等操作都只需要20行左右的代码就能实现，其代码量比较适合面试。
 * 总结：一是递归，链表是一个树的特殊结构；二是头插或者尾插
 */
public class ListStudy01 {

    /**
     * 题目一：反转一个单链表
     * @param args
     */
    public static void main(String[] args) {
        //创建一个单链表
        ListNode head = new ListNode(1);
        ListNode pre = head;
        for (int i = 2; i <= 10; i++){
            pre.next = new ListNode(i);
            pre=pre.next;
        }
        //遍历打印单链表
        printList(head);
        head = reverseList01(head);
        printList(head);
    }
    //打印单链表
    public static void printList(ListNode head){
        ListNode next = head;
        while (next != null){
            System.out.print(next.val);
            next = next.next;
        }
        System.out.println();
    }
    //方法一：使用头插法
    public static ListNode reverseList01(ListNode head){
        if (head == null) return head;
        //接管链表
        ListNode temp = head;
        //空出头节点
        head = null;
        ListNode tempNext;
        while (temp != null){
            tempNext = temp.next;
            //头插
            temp.next = head;
            head = temp;
            temp = tempNext;
        }
        return head;
    }
    /*public static ArrayList<Integer> printListFromTailToHead(ListNode head){
        ArrayList<Integer>
    }*/
    //方法二：使用分治法，递归解决问题
    //总结：递归体在什么位置决定了是树的什么遍历（前序、中序、后序），递归体用来解决问题
    //递归调用必须不停的向递归出口靠近，有返回值的是return xxx；没有返回值的是函数结束或者return;
//    public static ListNode reverseList02(ListNode head){
//        //递归出口
//        if (head == null|| head.next == null) return head;
//        ListNode temp = head.next;
//        head.next = temp.next;
//        temp.next = head;
//        head
//    }
}
